This invention relates to programmable logic devices in which long-carry-chain logic can be implemented. More particularly, this invention relates to programmable logic devices including circuitry for xe2x80x9cpredictingxe2x80x9d a carry result to speed up the remainder of a logic operation.
Programmable logic devices (xe2x80x9cPLDsxe2x80x9d) typically include (1) many regions of programmable logic, and (2) programmable interconnection resources for selectively conveying signals to, from, and/or between those logic regions. Each logic region is programmable to perform any of several different, relatively simple logic functions. The interconnection resources are programmable to allow the logic regions to work together to perform much more complex logic functions than can be performed by any individual logic region. Examples of known PLDs are shown in U.S. Pat. No. 3,473,160, U.S. Pat. No. Re. 34,363, U.S. Pat. Nos. 5,689,195 and 5,909,126, and U.S. patent application Ser. No. 09/266,235, all of which are hereby incorporated by reference herein in their entireties.
It is known to provide, in addition to the standard interconnection network, a xe2x80x9ccarryxe2x80x9d output from one logic region connected directly to a carry input of a neighboring logic region. This allows the second logic region to more quickly perform a logic function that depends on the carry output of the first logic region, because the direct carry connection allows the carry output to propagate more quickly to the second logic region than if it were routed on the general interconnection network.
The carry feature has several different uses. One use may be in arithmetic functions, such as addition where different logic regions are handling different bits of a multiple-bit addition problem. In such a case, except for the logic region handling the least significant bits, each logic region needs to know the value of the carry output from the logic region handling the bits of immediately lower significance. In some cases, many logic regions may be involved in a xe2x80x9clong-carry-chainxe2x80x9d calculation.
In a carry chain configuration, although the data for all logic regions may arrive substantially simultaneously, none of the regions can complete its operations until the carry arrives from the immediately preceding region. In a short carry chain, the delay involved in having each region wait for the preceding region is minimal. However, in a long carry chain, the cumulative delay at regions toward the end of the chain (e.g., the most significant bits in the arithmetic addition example) could be substantial.
It would be desirable to be able to provide a programmable logic device in which the values of carry signals could be predicted or determined in advance of completion of the operation forming the carry signal.
It is an object of this invention to provide a programmable logic device in which the values of carry signals can be predicted or determined in advance of completion of the operation forming the carry signal.
In accordance with the present invention, there is provided a programmable logic device having a plurality of regions of programmable logic. Each region has a plurality of input terminals and at least one output terminal, and each region is programmable to selectively perform any of a plurality of logic functions on input signals applied to the input terminals to produce an output signal applied to the output terminal. An interconnection network is programmable to selectively connect the output terminal of substantially any of the regions to at least one of the input terminals of substantially any of the regions. The programmable logic device is programmable to configure a plurality of the regions to perform a logic function requiring provision of at least one carry signal from one of the regions to another of the regions. The regions are arranged in groups, and the device further includes additional logic dedicated to propagating the carry signal to other regions without regard to completion of logic operations in the region. The additional logic includes circuitry for propagating the carry signal from one of the groups of regions to another of the groups of regions. That circuitry includes a carry-out in one of the groups for outputting a carry signal from that one of the groups and a carry-in in another of the groups for inputting a carry signal to that other group. The carry-in and the carry-out are arranged adjacent one another.
In accordance with another aspect of the invention, there is provided a programmable logic device having a plurality of regions of programmable logic, each having a plurality of input terminals and at least one output terminal, and each being programmable to selectively perform any of a plurality of logic functions on input signals applied to the input terminals to produce an output signal applied to the output terminal. An interconnection network is programmable to selectively connect the output terminal of substantially any of the regions to at least one of the input terminals of substantially any of the regions. The programmable logic device is programmable to configure a plurality of the regions to perform a logic function requiring provision of at least one carry signal from one of the regions to another of the regions. The device further comprises additional logic dedicated to propagating the carry signal to others of the regions without regard to completion of logic operations in the one region. The additional logic includes circuitry in the one region for calculating, separately from the logic function, the value for the carry signal to be input to the other regions as a function of a signal propagated into the first region.
In accordance with yet another embodiment of the invention, there is provided a programmable logic device comprising a plurality of regions of programmable logic, each having a plurality of input terminals and at least one output terminal, and each being programmable to selectively perform any of a plurality of logic functions on input signals applied to the input terminals to produce an output signal applied to the output terminal. An interconnection network is programmable to selectively connect the output terminal of substantially any of the regions to at least one of the input terminals of substantially any of the regions. The programmable logic device is programmable to configure a plurality of the regions into a chain of at least three regions to perform a logic function requiring provision of a carry signal from each of the regions to a subsequent region in the chain. The additional logic comprises circuitry in each of the regions for (i) receiving a carry signal from a region immediately preceding an immediately preceding region in the chain, (ii) receiving at least one propagation signal from the immediately preceding region in the chain, (iii) receiving at least one propagation signal from within the region, and (iv) producing a carry signal as a function of (1) the carry signal from the region immediately preceding the immediately preceding region in the chain, (2) the at least one propagation signal from the immediately preceding region, and (3) the at least one propagation signal from within the region.
In a preferred embodiment, the invention is implemented in a programmable logic device of the type described in copending, commonly-assigned U.S. patent application Ser. No. 09/516,921, filed concurrently herewith, which is hereby incorporated by reference herein in its entirety, and in above-incorporated U.S. Pat. No. 5,689,195 and applications Ser. Nos. 60/122,788 and 60/142,513. In such a programmable logic device, logic is arranged in regions, which are then arranged in groups or blocks spanning, preferably, ten rows of logic regions. The interconnection network includes local conductors, global conductors, and conductors of intermediate lengths.
In the preferred embodiment, each logic region preferably has four data inputs and the additional logic in each logic region is an arrangement of multiplexers that allow the logic region to calculate its logic function based on the two alternative carry-in possibilities, and then ultimately to select the correct result as the carry signal becomes available. The arrangement of multiplexers preferably also calculates both possible carry-out signals for the logic region, which in a chained configuration are provided as the two possible carry-in values to the next logic region in the logic chain.
In the arrangement just described, it is still necessary to wait for the carry values to propagate through the carry chain. However, the propagation of the carry values is still much faster than waiting for the carry values to be generated by the actual logic functions. Moreover, the wait can be further shortened by breaking the carry chain, which includes a plurality of regions, into smaller groups of regions, allowing the carry signals to propagate substantially simultaneously within all groups so that each group has two possible carry-out signals, and then propagating a carry-in signal into each group to allow selection of the correct carry-out signal, both within each region in the group, and at the group carry-out. The carry-in for each group will be the carry-out from the previous group, except in the case of the first group.
This arrangement means that the maximum wait for propagation of carry signals through the carry chain will be the time necessary for the alternative carry signals to propagate through the longest group. By the time that happens, each region, and each group, will have generated its respective pair of two alternative carry values. At that point, the initial carry-in to the first group will cause selection of the correct carry values for the regions in the first group and the first group itself. That group carry can be propagated relatively quickly to the next group, which has already finished its alternative carry signal generation process and is ready to select its final carry values, and so on to other groups through the end of the carry chain. This propagation from group to group, with no further computation involved, is very fast.
The speed at which the carry values are propagated can further be improved by the physical layout of the regions in a carry chain. For example, in the programmable logic device described in said above-incorporated U.S. Pat. No. 5,689,195, the logic regions are grouped in groups spanning ten rows of logic regions. It is frequently necessary to propagate a carry from one of those groups to an adjacent group, and indeed to do so through several groups. One might think to arrange the regions within each group linearly, so that the carry propagates into the group at the top of the column and is propagated out at the bottom of the column. In such an arrangement, it is necessary to wait for the carry generation process to propagate through an entire group before the correct carry can be propagated to the next group. In addition, there is a small but measurable further delay as the carry signal propagates back up to the top of the next column, which has completed its own carry generation process but is waiting for the carry from the previous group.
Therefore, in accordance with the invention, the logic regions are laid out so that if a carry chain is to be created by the programming of the programmable logic device, the carry chain may be broken into two halves, with the first half starting at the top of a column and ending in the middle, and the second half starting at the bottom of that column and ending in the middle. This has two advantages.
First, the groups of regions in a carry chain are broken into smaller groups, so that the time that must elapse for the carry generation process to propagate through each group is reduced. Second, the carry outputs of each group are arranged physically closer to one another, so that the time needed for propagation from one group to the next, so that each group can select its final carry value, is also reduced. In another embodiment, the groups are not broken into smaller groups, but the carry signals are propagated horizontally from each group to a multiplexer or similar element at the end of the next group which has received the internal carry generation results of its own group and uses the carry signal to make a final selection. The carry signal is also propagated backwards through the second group to the individual regions in the second group so that they can complete their individual logic functions. This at least eliminates the short propagation delay that would result from propagating the carry signal from the bottom of one group to the top of the next group.
In a second preferred embodiment, rather than propagating across groups, the carry is propagated forward by two regionsxe2x80x94i.e., a carry propagated from one region skips the immediately adjacent region and propagates to the next following region. That next following region is able to predict the correct carry value of the skipped region from the propagated value of the previous region and other inputs, as described below. In this embodiment, there are effectively two carry chains, as each skipped region in the first chain propagates its carry to the region following the region immediately adjacent it. In this second carry chain, the skipped regions are the regions of the first chain, and vice-versa. This arrangement achieves about a 50% time savings in the carry chain as compared to not implementing any form of carry look-ahead.
In third and fourth embodiments, the carry is predicted by implementing in the logic a mathematical prediction as described below. Preferably, this is done once for each group, and the carries are propagated horizontally in a manner similar to the alternative version of the first embodiment, as described above. In these third and fourth embodiments, the carry chain can be broken down into smaller groups of regions to speed up the carry prediction, as described above in connection with the first embodiment.
The first embodiment has the advantage that it can predict the carry values for any type of chained logic function. The second, third and fourth embodiments, on the other hand, function only when the chained logic is part of an arithmetic operation, such as an adder chain.